package com.leetcode.algorithm.y19.m03;

import java.util.Arrays;

import com.leetcode.algorithm.common.TreeNode;

/**
 * leetcode-cn.com
 * (done)106. 从中序与后序遍历序列构造二叉树
 * (done)105. 从前序与中序遍历序列构造二叉树
 * (done)889. 根据前序和后序遍历构造二叉树
 * @author: jie.deng
 * @time: 2019年3月10日 上午12:10:19
 */
public class MySolution0310 {
	/**
	 * 106. 从中序与后序遍历序列构造二叉树
	 * 
	 * 根据一棵树的中序遍历与后序遍历构造二叉树。
	 * 
	 * 注意:
	 * 你可以假设树中没有重复的元素。
	 * 
	 * 例如，给出
	 * 
	 * 中序遍历 inorder = [9,3,15,20,7]
	 * 后序遍历 postorder = [9,15,7,20,3]
	 * 返回如下的二叉树：
	 * 
	 *     3
	 *    / \
	 *   9  20
	 *     /  \
	 *    15   7
	 * @param inorder
	 * @param postorder
	 * @return
	 */
	public TreeNode buildTree(int[] inorder, int[] postorder) {
		int len = inorder.length;
		if (len == 0) {
			return null;
		}
		if (len == 1) {
			return new TreeNode(inorder[0]);
		}
		// 找根结点:后序遍历的最后一个元素
		int val = postorder[postorder.length - 1]; // 后续遍历，最后一个元素为根结点
		TreeNode root = new TreeNode(val);
		// 左子树
		int idx = 0;
		for (int i = 0; i < len; i++) {
			if (inorder[i] == val) {
				idx = i; // 找中序遍历 根结点的索引，该索引左边为左子树、右边为右子树
				break;
			}
		}
		if (idx > 0) {
			root.left = buildTree(Arrays.copyOfRange(inorder, 0, idx), Arrays.copyOfRange(postorder, 0, idx));
		}
		// 右子树
		if (idx < len - 1) {
			root.right = buildTree(Arrays.copyOfRange(inorder, idx + 1, len),
					Arrays.copyOfRange(postorder, idx, len - 1));
		}
		return root;
	}

	/**
	 * 105. 从前序与中序遍历序列构造二叉树
	 * 
	 * 根据一棵树的前序遍历与中序遍历构造二叉树。
	 * 
	 * 注意:
	 * 你可以假设树中没有重复的元素。
	 * 
	 * 例如，给出
	 * 
	 * 前序遍历 preorder = [3,9,20,15,7]
	 * 中序遍历 inorder = [9,3,15,20,7]
	 * 返回如下的二叉树：
	 * 
	 *     3
	 *    / \
	 *   9  20
	 *     /  \
	 *    15   7
	 * @param preorder
	 * @param inorder
	 * @return
	 */
	public TreeNode buildTreeII(int[] preorder, int[] inorder) {
		int len = inorder.length;
		if (len == 0) {
			return null;
		}
		if (len == 1) {
			return new TreeNode(inorder[0]);
		}
		// 找根结点:前序遍历的第一个元素
		int val = preorder[0];
		TreeNode root = new TreeNode(val);
		// 左子树
		int idx = 0;
		for (int i = 0; i < len; i++) {
			if (inorder[i] == val) {
				idx = i; // 找中序遍历 根结点的索引，该索引左边为左子树、右边为右子树
				break;
			}
		}
		if (idx > 0) {
			root.left = buildTreeII(Arrays.copyOfRange(preorder, 1, idx + 1), Arrays.copyOfRange(inorder, 0, idx));
		}
		// 右子树
		if (idx + 1 < len) {
			root.right = buildTreeII(Arrays.copyOfRange(preorder, idx + 1, len),
					Arrays.copyOfRange(inorder, idx + 1, len));
		}
		return root;
	}

	/**
	 * 889. 根据前序和后序遍历构造二叉树
	 * 
	 * 返回与给定的前序和后序遍历匹配的任何二叉树。
	 * 
	 *  pre 和 post 遍历中的值是不同的正整数。
	 * 
	 *  
	 * 
	 * 示例：
	 * 
	 * 输入：pre = [1,2,4,5,3,6,7], post = [4,5,2,6,7,3,1]
	 * 输出：[1,2,3,4,5,6,7]
	 *  
	 * 
	 * 提示：
	 * 
	 * 1 <= pre.length == post.length <= 30
	 * pre[] 和 post[] 都是 1, 2, ..., pre.length 的排列
	 * 每个输入保证至少有一个答案。如果有多个答案，可以返回其中一个。
	 * @param pre
	 * @param post
	 * @return
	 */
	public TreeNode constructFromPrePost(int[] pre, int[] post) {
		int len = pre.length;
		if (len == 0) {
			return null;
		}
		// 找根结点:前序遍历的第一个元素
		int val = pre[0];
		TreeNode root = new TreeNode(val);
		if (len == 1) {
			return root;
		}
		// 找左子树根结点:前序遍历的第二个元素
		int leftVal = pre[1];
		int idx = 0;
		for (int i = 0; i <= len - 2; i++) {
			if (post[i] == leftVal) {
				idx = i; // 找后序遍历 左子树的根结点的索引，该索引左边为左子树(包含当前索引)、右边为右子树(不包含最后一个结点)
				break;
			}
		}
		root.left = constructFromPrePost(Arrays.copyOfRange(pre, 1, idx + 2), Arrays.copyOfRange(post, 0, idx + 1));
		// 剩余的为右子树
		if (idx < len - 2) {
			root.right = constructFromPrePost(Arrays.copyOfRange(pre, idx + 2, len),
					Arrays.copyOfRange(post, idx + 1, len - 1));
		}
		return root;
	}
}
